/**
 * 
 */
package datastructure2;

import java.util.HashMap;
import java.util.Map;

/**
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
 */
public class LRUCache {

	class Node {
		Node prev = null;
		Node next = null;
		Integer val;
		Integer key;
		public Node(int key, int val) {
			this.key = key;
			this.val = val;
		}
	}
	
	private Map<Integer, Node> storage = null;
	private Node head = null;
	private int capacity = 0;
	
	/**
	 * 
	 */
	public LRUCache() {
		this(10);
	}

	public LRUCache(int capacity) {
		this.capacity = capacity;
		storage = new HashMap<>(capacity);
	}
	
    public int get(int key) {
    	int result = -1;
    	if (storage.containsKey(key)) {
    		Node node = storage.get(key);
    		result = node.val;
    		detach(node);
    		attach(node);
    	}
    	
    	return result;
    }
    
    public void set(int key, int value) {
    	Node node = null;
        if (storage.containsKey(key)) {
        	node = storage.get(key);
        	node.val = value;
        	detach(node);
        }
        else {
        	// ptifall if cache is full detach last onde and remove the key from storage
        	if (storage.size() == capacity) {
        		Node tail = head.prev;
        		detach(tail);
        		storage.remove(tail.key);
        	}
        	node = new Node(key, value);
        	storage.put(key, node);
        }
        attach(node);
    }	
    
    private void detach(Node node) {
    	if (node == head) {
    		head = head.next;
    	}
    	node.prev.next = node.next;
    	node.next.prev = node.prev;
    }
    
    private void attach(Node node) {
    	if (head == null) {
    		head = node;
    		head.next = node;
    		head.prev = node;
    	}
    	else {
    		node.prev = head.prev;
    		node.next = head;
    		node.prev.next = node;
    		node.next.prev = node;
    		head = node;
    	}
    }
	
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
